The invention relates to the general field of cryptography and of protecting digital data.
The invention relates more particularly to a method enabling a so-called “trusted” entity to securely delegate calculation of a value of a bilinear pairing or mapping to a calculation server.
The invention thus applies in preferred but non-limiting manner to numerous cryptographic protocols (in particular public key protocols, such as cryptographic protocols for digitally signing messages) that make use of complex mathematical tools known as bilinear pairings.
Numerous cryptographic protocols have recently come into use in the field of telecommunications, and in particular in mobile communications, in order to enable various actors in that field (e.g. operators, service providers, etc.) to provide their clients with new functions and/or services, while guaranteeing protection and respect for their private lives. Those protocols often require the use of mathematical techniques that are complex, such as bilinear pairings.
It should be recalled that a bilinear pairing, written e, is a mapping (or map) defined on a set G1×G2 to a set GT contained in a group G, where G1, G2, and GT generally designate cyclic groups of order p, where p is a prime number. This mapping e satisfies the following properties:
(1) Bilinearity:∀X1ϵG1,∀X2ϵG2,∀(a,b)ϵZp,e(aX1,bX2)=e(X1,X2)ab where Zp designates the set of relative integers less than p.(2) Non-degenerate: for X1≠1G1 and X2≠1G2, e(X1, X2)≠1GT where 1G1, 1G2 and 1GT designate respectively the unities of the sets G1, G2, and GT.(3) Calculable: there exists an efficient algorithm for calculating e(X1,X2), ∀X1ϵG1, ∀X2ϵG2.
Although such bilinear pairings have been known for a long time, their applications to the field of cryptography is relatively recent. Furthermore, implementing these tools requires a large amount of computation power, which makes them difficult to use in practice by low power entities such as, for example: a smart card such as a mobile identity card or subscriber identity module (SIM) card.
A conventional solution for remedying that drawback consists in delegating the calculation of bilinear pairings to a more powerful entity, which is referred to in this description in general manner as a calculation server. Thus, for example, for a SIM card, the calculation server may be the telephone in which the SIM card is inserted.
It should be observed that delegating the calculation of bilinear pairings may be envisaged in other circumstances. Thus, for example, a computer may also find it advantageous to delegate certain cryptographic calculations to a remote computer server in order to release time for other processes (whether cryptographic or otherwise).
Although the calculation server is capable of carrying out the bilinear pairing calculation that has been delegated thereto in efficient manner, it does not necessarily provide the same guarantees in terms of security as the entity that delegated the calculation. By way of illustration, in the above example, although the SIM card of a mobile telephone constitutes a secure element, that is not true of the telephone that receives it, which may be corrupted by malicious applications such as viruses.
Consequently, an important problem that arises when a so-called trusted entity delegates the calculation of a bilinear pairing to a calculation server, is the verifiability of the bilinear pairing value supplied by the calculation server. In other words, it is important for the trusted entity to be capable of being sure that the bilinear pairing value that has been calculated and supplied by the calculation server is correct. It should be observed that a trusted entity that accepts and uses a bilinear pairing value as evaluated by a remote server in a cryptographic protocol, but without taking care to verify that value, exposes itself to severe security problems that may go well beyond mere denial of service: by way of example, accepting an invalid digital signature issued by a malicious entity might lead to sensitive data being transmitted to that entity.
In an article entitled “Secure delegation of elliptic-curve pairing”, IACR Cryptology ePrint Archive 2005, Chevallier-Mames et al. propose a mechanism enabling a trusted entity to delegate a bilinear pairing calculation to a calculation server that enables the bilinear pairings that are evaluated by the calculation server to be verified by the trusted entity. Nevertheless, that mechanism is not very efficient in terms of resources: seven exponentiations in the group GT are required to guarantee such verifiability (where exponentiations are the operations that are most expensive in terms of complexity), such that the delegation mechanism proposed by Chevallier-Mames would appear to be difficult to use in practice.
There therefore exists a need for a secure mechanism for delegating a bilinear pairing value to a calculation server that enables the value returned by that server to be verified provided an efficient and reasonable (i.e. small) implementation in terms of complexity.